package dynamicStudy;

/**
 * Coin Change
 *  (1)有三种硬币，面值分别为2元、5元、7元，每种硬币足够多
 * （2）买一本书需要27元
 * （3）如何用最少的硬币组合正好付清，不需要对方找钱
 * 分析：这类题目是求最大最小的动态规划问题
 * 用一维数组解决最优解问题
 *
 * 第二步：
 *      设状态f[X] = 最少用多少枚硬币拼出X
 *
 *
 */
public class CoinChange {

    public static void main(String[] args) {
        int[] a = {2, 5, 7};
        int i = coinChange(a, 27);
        System.out.println(i);
    }

    public static int coinChange(int[] a, int m){
        //开辟空间，也添加了一个为0的数组
        int[] f = new int[m + 1]; //隐式初始化，所有值都为0
        int n = a.length; //number of kinds of coins
        //初始化
        f[0] = 0;
        //f[0], f[2], ..., f[27]
        for (int i = 1; i <= m; i++){
            //将所有状态都初始化为最大值，因为需要求最小，
            f[i] = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++){
                if (i>=a[j] && f[i - a[j]] != Integer.MAX_VALUE){
                    //得到最优解
                    f[i] = Math.min(f[i - a[j]] + 1, f[i]);
                }
            }
        }
        if (f[m] == Integer.MAX_VALUE){
            f[m] = -1;
        }
        return f[m];
    }
}
